package com.hackerrank.challenges.findmedian;

import java.util.Scanner;

public class Solution {
	/**
	 * Selects the kth-smallest element in a and places it
	 * in the kth position of a[]. The remaining elements are
	 * rearranged such that a[m] <= a[k] for 0 <= m < k, and
	 * a[m] >= a[k] for k < m < a.length
	 * @param a
	 * @param n
	 * @param k
	 * @return
	 */
	private static int findKthElement(int a[], int k) {
		int low = 0, up = a.length;
		while(true) {
			// Each time the loop is entered,
			// 0 <= low <= k <= up <= a.length
			int j = partition(a, low, up);
			// j is such that a[j] is the jth-smallest value in a[].
			if(k == j)
				return a[k];
			if(k < j)
				up = j; // j is the new upper limit.
			else
				low = j + 1; // j + 1 is the new lower limit.
		}
	}
	/**
	 * Exchange a[i] with a[j].
	 * @param a
	 * @param i
	 * @param j
	 */
	private static void interchange(int a[], int i, int j) {
		int p = a[i];
		a[i] = a[j];
		a[j] = p;
	}
	/**
	 * Within a[m], a[m + 1],..., a[p - 1] the elements are
	 * rearranged in such a manner that if initially t = a[m],
	 * then after completion a[q] = t for some q between m
	 * and p - 1, a[k] <= t for m <= k < q, and a[k] >= t
	 * for q < k < p. q is returned. Set a[p] = infinity.
	 * @param a
	 * @param m
	 * @param p
	 * @return
	 */
	private static int partition(int a[], int m, int p) {
		int v = a[m], i = m, j = p;
		while(i < j) {
			while(a[++i] < v);
			while(a[--j] > v);
			if(i < j)
				interchange(a, i, j);
		}
		a[m] = a[j];
		a[j] = v;
		return j;
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), a[] = new int[n];
		for(int i = 0; i < n; i++)
			a[i] = in.nextInt();
		System.out.println(findKthElement(a, a.length / 2));
	}
}
